package main

import (
	"fmt"
)

func maxHeapify(heap []int, start, end int) {
	root := start
	for {
		child := 2*root + 1
		if child > end {
			break
		}
		if child+1 <= end && heap[child] < heap[child+1] {
			child++
		}
		if heap[root] < heap[child] {
			heap[root], heap[child] = heap[child], heap[root]
			root = child
		} else {
			break
		}
	}
}

func HeapSort(a []int) {
	n := len(a)
	// Build the heap
	for start := (n - 2) / 2; start >= 0; start-- {
		maxHeapify(a, start, n-1)
	}
	// Extract elements from the heap
	for end := n - 1; end > 0; end-- {
		a[0], a[end] = a[end], a[0]
		maxHeapify(a, 0, end-1)
	}
}

func main() {
	array := []int{2, 4, 5, 1, 3, 123, 8, 234, 3, 56, 1, 123, 312, 452, 34}
	HeapSort(array)
	fmt.Println("Sorted array:", array)
}
